#include <iostream>
#include <cmath>
using namespace std;

inline void intro()
{
    cout << endl
         << "学号：3170608043，姓名：石英钰" << endl
         << endl
         << "Features: 二分法排序" << endl
         << endl;
}

int main()
{
    intro();
    int a[] = {53, 21, 23, 4, 54, 32, 34, 43, 44, 90, 91};
    int n = sizeof(a) / sizeof(a[0]);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; i + j < n - 1; j++)
        {
            if (a[j] < a[j + 1])
            {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }

    // 快速排序法
    // for (int i = 0; i < n - 1; i++) // 前
    // {
    //     for (int j = i + 1; j < n; j++) // 后
    //     {
    //         if (a[i] < a[j])
    //         {

    //         }
    //     }
    // }

    for (int i = 0; i < n; i++)
    {
        printf("%d, %d\n", i + 1, a[i]);
    }

    int query;
    cout << "请输入要查找的元素值:";
    cin >> query;
    // for (int i=0;i<n;i++){
    //     if (a[i] == query){
    //         printf("%d, %d\n",i+1,a[i]);
    //         return 0;
    //     }
    // }

    if (a[0] == query)
    {
        printf("%d, %d\n", 0 + 1, a[0]);
    }
    else if (a[n - 1] == query)
    {
        printf("%d, %d\n", n, a[n - 1]);
    }
    else
    {
        int x = 1, y = n, mid = 0;
        for (;;)
        {
            mid = (x + y) / 2;
            if (a[mid - 1] == query)
            {
                printf("%d, %d\n", mid, a[mid - 1]);
                break;
            }
            x = a[mid - 1] > query ? mid : x;
            y = a[mid - 1] < query ? mid : y;
            if (abs(x - y) <= 1)
            {
                cout << "没找到" << endl;
                break;
            }
        }
    }

    return 0;
}